class Solution:
    def floodFill(self, image, sr: int, sc: int, newColor: int):
        nextPoints = ((-1, 0), (1, 0), (0, -1), (0, 1))
        oldColor = image[sr][sc]
        if newColor == oldColor:
            return image
        queue = [(sr, sc)]
        while len(queue) > 0:
            point = queue.pop(-1)
            if image[point[0]][point[1]] == oldColor:
                image[point[0]][point[1]] = newColor
                for p in nextPoints:
                    if 0 <= point[0] + p[0] < len(image) and 0 <= point[1] + p[1] < len(image[point[0] + p[0]]) and \
                            image[point[0] + p[0]][point[1] + p[1]] == oldColor:
                        queue.append((point[0] + p[0], point[1] + p[1]))
        # print(oldColor)
        return image


if __name__ == '__main__':
    so = Solution()
    image = [[0,0,0],[0,1,1]]
    sr = 1
    sc = 1
    newColor = 1
    r = so.floodFill(image, sr, sc, newColor)
    print(r)
